package test0819;

/**
 * Created with IDEA
 * author:ju bai
 * Date:2021/8/19
 * Time:14:00
 **/
public class Main2 {
    //非递归
    public int binarySearch (int[] arr, int num) {
        int low = 0;
        int high = arr.length-1;
        while(low < high) {
            int mid = (low+high)/2;
            if(arr[mid] == num) {
                return mid;
            }else {
                //若中间值>要找的值，说明要找的值在左半部分，将high置为mid-1
                if(arr[mid] > num) {
                    high = mid-1;
                }else {
                    low = mid +1;
                }
            }
        }
        return -1;
    }
    //递归
    public int binarySearch2 (int[] arr, int num,int low,int high) {
        if(low > high) {
            return -1;
        }else {
            int mid = (low+high)/2;
            if(arr[mid] == num) {
                return mid;
            }else if(arr[mid] > num) {
                return binarySearch2(arr,num,low,high-1);
            }else {
                return binarySearch2(arr,num,mid+1,high);
            }
        }
    }
}
